/**
 * 464. 我能赢吗
 * https://leetcode.cn/problems/can-i-win/
 */

/**
 * @param {number} maxChoosableInteger
 * @param {number} desiredTotal
 * @param {number} chosenIntegers
 * @param {number} currentTotal
 * @param {Map<number, boolean>} memory
 * @return {boolean}
 */
function dfs(maxChoosableInteger, desiredTotal, chosenIntegers, currentTotal, memory) {
  if (memory.has(chosenIntegers)) {
    return memory.get(chosenIntegers);
  }
  let result = false;
  for (let i = 1; i <= maxChoosableInteger; i += 1) {
    if (!((1 << i) & chosenIntegers)) {
      const nextTotal = currentTotal + i;
      if (nextTotal >= desiredTotal) {
        result = true;
        break;
      }
      if (!dfs(maxChoosableInteger, desiredTotal, chosenIntegers | (1 << i), nextTotal, memory)) {
        result = true;
        break;
      }
    }
  }
  memory.set(chosenIntegers, result);
  return result;
}

/**
 * @param {number} maxChoosableInteger
 * @param {number} desiredTotal
 * @return {boolean}
 */
function canIWin(maxChoosableInteger, desiredTotal) {
  if (((1 + maxChoosableInteger) * maxChoosableInteger) / 2 < desiredTotal) {
    return false;
  }
  return dfs(maxChoosableInteger, desiredTotal, 0, 0, new Map());
}

console.log(canIWin(10, 11) === false);
console.log(canIWin(10, 0) === true);
console.log(canIWin(10, 1) === true);
console.log(canIWin(5, 50) === false);
